Việc tiên đề hóa (axiomatization) toán học, theo mô hình tác phẩm Elements của Euclid, đã đạt đến một mức độ rộng và chặt chẽ mới vào cuối thế kỉ 19, đặc biệt là trong số học (nhờ vào công Richard Dedekind và Giuseppe Peano) và hình học (nhờ vào công của David Hilbert). Tuy nhiên, vào đầu thế kỉ 20, lý thuyết tập hợp, một ngành toán mới phát minh bởi Georg Cantor, và được đẩy vào chỗ khủng hoảng bởi Bertrand Russell với sự khám phá ra nghịch lý nổi tiếng của ông ta (về tập hợp của các tập hợp không thuộc chính nó), đã chưa được công thức hóa. Nghịch lý Russell bao gồm quan sát rằng nếu như tập hợp x (của tập các tập hợp không phải là thành viên của chính nó) là một thành viên của chính nó, thì nó phải thuộc về tập hợp các tập hợp không thuộc về chính nó, và do vậy không thể thuộc về chính nó; mặt khác, nếu như tập x không thuộc chính nó, thì nó phải thuộc tập của các tập hợp không thuộc chính nó, và do vậy nó phải thuộc về chính nó.

Vấn đề tiên đề hóa lý thuyết tập hợp đã được giải quyết một cách tiềm ẩn khoảng hai mươi năm sau (nhờ vào công của Ernst Zermelo và Abraham Frankel) bằng cách một chuỗi các nguyên lý được cho phép trong việc xây dựng tất cả các tập hợp được sử dụng thật sự trong toán học, nhưng không loại trừ một cách rõ rệt khả năng tồn tại những tập hợp thuộc về chính nó. Trong luận án tiến sĩ năm 1925, von Neumann chứng tỏ có thể loại bỏ khả năng đó trong hai cách bù trừ lẫn nhau: "tiên đề nền tảng" và khái niệm "lớp".

Tiên đề nền tảng thiết lập rằng tất cả các tập hợp đều có thể xây dựng từ dưới lên trong một các bước theo thứ tự kế tiếp nhau bằng các nguyên lý của Zermelo và Frankel, trong một cách thức rằng nếu một tập hợp thuộc về một tập khác thì tập thứ nhất cần phải đi trước tập thứ hai trong trật tự (do vậy loại trừ khả năng một tập hợp thuộc về chính nó.) Để biểu diễn rằng sự thêm vào của các tiên đề mới vào các tiên đề khác không sản sinh ra các mâu thuẫn, von Neumann giới thiệu một phương pháp biểu diễn (gọi là "phương pháp các mô hình nội tại") mà sau này trở thành những công cụ quan trọng của lý thuyết tập hợp.

Cách tiếp cận thứ hai của vấn đề dựa vào khái niệm lớp (class), và định nghĩa một tập hợp như là một lớp thuộc về các lớp khác, trong khi một "lớp nhỏ hơn" được định nghĩa như là một lớp không thuộc về lớp nào khác. Trong khi, trong cách tiếp cận của Zermelo/Frankel, những tiên đề cản trở việc xây dựng một tập hợp của các tập hợp không thuộc về chính nó, trong cách tiếp cận của von Neumann, lớp của các tập hợp không thuộc về chính nó có thể được xây dựng, nhưng nó là một "lớp nhỏ hơn" chứ không phải là một tập hợp.

Với đóng góp này của von Neumann, hệ thống các tiên đề của lý thuyết tập hợp trở thành đủ hoàn chỉnh, và câu hỏi kế tiếp là liệu là nó đã xác định hay chưa, mà không cần phải cải tiến. Một câu trả lời phủ định khá mạnh đưa ra vào tháng 9 năm 1930 tại Hội nghị toán học lịch sử tại Konigsberg, mà trong đó Kurt Gödel công bố "định lý đầu tiên về sự không toàn vẹn" nổi tiếng của ông: các hệ thống tiên đề thông thường là không hoàn toàn, theo ý nghĩa là chúng không thể chứng minh được tất cả những sự thật có thể diễn tả được trong ngôn ngữ của hệ thống đó. Kết quả này đủ mới để làm bối rối các nhà toán học của thời gian đó. Nhưng von Neumann, tham dự trong hội nghị đó, đã khẳng định tiếng tăm của ông như một người suy nghĩ ra vấn đề ngay tức khắc, và dưới một tháng sau đã có khả năng liên lạc với chính Gödel một hệ quả thú vị của định lý của ông: những hệ thống tiên đề thông thường là không có khả năng diễn tả sự nhất quán của chính chúng. Chính xác là hệ quả này đã thu hút được nhiều sự chú ý nhất, ngay cả nếu như nguyên thủy Gödel chỉ xem nó như là một điều tò mò, và có thể suy ra nó một cách độc lập (chính vì lý do này mà kết quả được gọi là "định lý Gödel thứ hai", mà không nhắc đến tên của von Neumann).